The invention relates generally to computer systems, and deals more particularly with a technique for allocating locations on DASD to store data; the allocation efficiently uses available storage in the DASD and minimizes overhead associated with accessing of the data on DASD.
In many computer systems, such as an IBM VM/ESA 1.1 computer system, external storage is provided by a direct access storage device (DASD). The DASD can comprise one or more magnetic disks. If more than one magnetic disks is included in the DASD, they are stacked as "platters" along a common axis. Each of the disks comprises a large number of coaxial circular tracks to store the data. If the DASD comprises a single disk, then a single read/write head is provided. The disk rotates such that when the read/write head is stationary, the read/write head can read all the information stored on a track during one complete rotation of the disk. The read/write head can also move radially to read other tracks. If the DASD comprises multiple disks, then one read/write head is provided for each disk. All the read/write heads are aligned under the same location of each disk and fixedly connected to each other to move in unison. Only one read/write head is sensed at any one time. A "cylinder" is defined as a collection of circular tracks, one per disk, that are vertically aligned. For a DASD comprising multiple disks, an extent comprises one or more cylinders. To read one cylinder, the DASD is rotated a number of times equal to the number of platters, and during each rotation, a different one of the read/write heads is sensed. To read one extent of the type comprising multiple adjacent cylinders, the foregoing process is repeated for each cylinder with a corresponding radial movement of the read/write head.
In the foregoing DASD arrangements, one factor which limits the speed of accessing (writing to or reading from) the DASD, is the time required to move the read/write head(s) radially from cylinder to another. Therefore, it is desirable to minimize the amount of radial movement of the read/write head required for each access. If the allocated addresses are not contiguous, then the allocated addresses may be radially spaced from each other, and require additional radial movement of the read/write head between the spaced addresses. A second factor which limits the speed of accessing the DASD is the time required for the data to rotate so that it is positioned under the read/write heads. Therefore, it is desirable to minimize the amount of rotational movement required for each access. When I/O is performed to non-contiguous addresses, extra time is required to allow the data that is not being accessed to pass under the read/write heads. A third factor is the number of I/O operations required to complete the access. An I/O subsystem controls the DASD and must specify a start location on DASD and length information for each discontiguous set of storage locations. Therefore, it is desirable to minimize the number of I/O operations that are required for each I/O access. If the data to be written to DASD can all be stored in one contiguous set of locations in DASD, then a single I/O operation suffices because only one start location and one length need be specified. However, if there is not one contiguous set of locations which is available to accomodate all the data, then the data must be split between discontiguous of locations, and this requires one I/O operation for each discontiguous set.
A fourth factor in managing the DASD is to avoid waste of storage capacity. Unfortunately, during continued usage of the DASD the available storage areas may become fragmented. For example, assume that ten pages of data (4,096 bytes per page) are stored in a fully utilized area of DASD. Each page utilizes one "slot" of storage. Next, an application program requests access to the ten pages, and the ten pages are written into main storage (RAM) to facilitate such access. The application program modifies eight of the ten pages and adds a page, but does not change the other two original pages. Subsequently, the operating system detects that the main storage is nearly full, and initiates a "block paging" operation to free-up the main storage by writing some of the pages in the main storage to DASD. There are various criteria by which the operating system decides which pages to write to DASD to free-up the main storage. According to one common criterion, the operating system selects a group of pages that were accessed at approximately the same time. This may lead to the selection of all of the foregoing ten pages. However, to minimize the amount of I/O work, the two unchanged pages are not written back to DASD; the original copy on the DASD is still valid. Therefore, only the eight updated pages and the additional page must be written to DASD, but the original location in the congested area can only store eight pages in contiguous locations. Therefore, a new location must be selected to store some or all of the nine pages. If a single set of nine contiguous slots is sought to minimize the number of I/O operations and limit radial movement of the read/write head, there will be an isolated set of eight contiguous slots which is available for other data. This process frequently repeats so that over time, there may be many isolated sets of different numbers of available slots on the DASD. To avoid wasting available storage on the DASD, techniques must be used to either avoid creating such isolated sets or to locate and use them for subsequent write operations. However, as noted above, the number of I/O operations and amount of radial head movement and rotational delay should be minimized.
One prior art technique logically divides the DASD into sets of slots of a fixed size, for example, ten slots per set. Whenever the operating system needs to write data to DASD, one or more of such sets is allocated to accomodate the request. Because of other criteria which govern the amount of data to be written to DASD, the amount of data to be written is often less than the allocation. This wastes storage capacity and leaves gaps which require rotational movement to bypass. Also, if the data to be written requires more than one set of the slots, then two or more I/O operations are normally required. The two or more sets are selected by a "moving cursor" which steps through the DASD in ascending DASD address to satisfy each successive request.
Another prior art technique utilizes a moving cursor to step through the DASD in ascending DASD address to satisfy each storage request made by the operating system. According to this technique, the allocations are not restricted to sets of fixed size, but instead attempt to precisely match the length of the storage request. As the moving cursor proceeds through the DASD to satisfy new requests, some of the data previously written to the DASD is accessed, i.e. read into main storage. Then a subset of those pages may be modified or regrouped and rewritten to a new DASD address, freeing the old DASD locations. This leaves gaps in the DASD. Another operating system function constantly monitors the availability of storage behind the cursor, and when seventy five percent of the slots behind the cursor become available, the cursor is moved back to the beginning. Then, the cursor moves forward again and allocates the available slots in order of location on the DASD to accomodate subsequent requests. While this technique minimizes the amount of available sets of isolated slots, the technique tends to fragment the storage of related data requiring extra I/O operations and radial and rotational movement of the read/write head.
Accordingly, a general object of the present invention is to provide a computer system, program or method which allocates DASD to minimize the number of I/O operations required to accomodate the data to be written to DASD, yet efficienlty utilizes the available storage on the DASD.
Another object of the present invention is to provide a computer system, program or method of the foregoing type which minimizes the amount of radial read/write head movement and rotational movement required to access the data.